# 617.合并二叉树
# 给你两棵二叉树： root1和root2 。
# 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果
# 两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为null的节点将直接作为新二叉树的节点。
# 返回合并后的二叉树。
# 注意: 合并过程必须从两个树的根节点开始。
#
# 示例1：
# 输入：root1 = [1, 3, 2, 5], root2 = [2, 1, 3, null, 4, null, 7]
# 输出：[3, 4, 5, 5, 4, null, 7]
#
# 示例2：
# 输入：root1 = [1], root2 = [1, 2]
# 输出：[2, 2]


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def mergeTrees(self, root1: [TreeNode], root2: [TreeNode]) -> [TreeNode]:
        # 1.确定递归函数和返回值
        def traver(root1,root2):
            # 2.确定终止条件
            if not root1 and not root2:
                return None
            if not root1:
                return root2
            if not root2:
                return root1
            root1.val += root2.val
            root1.left = traver(root1.left,root2.left)
            root1.right = traver(root1.right,root2.right)
            return root1
        return traver(root1,root2)

    # 还有迭代法，还没仔细看，先拿过来吧
    def mergeTrees2(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1:
            return root2
        if not root2:
            return root1
        from collections import deque
        queue = deque()
        queue.append(root1)
        queue.append(root2)

        while queue:
            node1 = queue.popleft()
            node2 = queue.popleft()
            # 更新queue
            # 只有两个节点都有左节点时, 再往queue里面放.
            if node1.left and node2.left:
                queue.append(node1.left)
                queue.append(node2.left)
            # 只有两个节点都有右节点时, 再往queue里面放.
            if node1.right and node2.right:
                queue.append(node1.right)
                queue.append(node2.right)

            # 更新当前节点. 同时改变当前节点的左右孩子.
            node1.val += node2.val
            if not node1.left and node2.left:
                node1.left = node2.left
            if not node1.right and node2.right:
                node1.right = node2.right

        return root1


if __name__ == '__main__':
    a3 = TreeNode(5)
    a21 = TreeNode(3,a3)
    a22 = TreeNode(2)
    a11 = TreeNode(1,a21,a22)
    b31 = TreeNode(4)
    b32 = TreeNode(7)
    b21 = TreeNode(1,right=b31)
    b22 = TreeNode(3,right=b32)
    b11 = TreeNode(2,b21,b22)
    tmp = Solution()
    # res = tmp.mergeTrees(root1=a11,root2=b11)
    res = tmp.mergeTrees2(root1=a11,root2=b11)
    print(res)
